/*
实验1-1 有序数组的插入
分数 20
作者 陈越
单位 浙江大学

给定存储了 n 个从大到小排好序的整数，试将任一给定整数 x
插入数组中合适的位置，以保持结果依然有序。分析算法在最坏、最好情况下的时间、空间复杂度。
具体来说，不妨假设整数序列存储为一个序列
array，这个序列的结构定义在下面给出，数据存放在数组 data
中。因为数组长度是有限的，我们在此假设 data 数组的最大长度为
kMaxSize。如果在执行插入之前，数组已经满了，则插入失败，返回
false；如果待插入的元素 x 已经在 data 中，则不要重复插入，返回
false；如果插入成功，则返回 true。 函数接口定义：

bool DecrSeqInsert( ArrPtr array, ElemSet x );

其中ArrPtr结构定义如下：

typedef int Position;  // 整型下标，表示元素的位置

typedef struct ArrNode *ArrPtr;

struct ArrNode {
    ElemSet *data; // 存储数据的数组；ElemSet是用户定义的数据类型
    int size;      // 数组的大小
};

函数接口定义中，ElemSet 是用户定义的数据类型，例如 int、double 或者 char
等，要求可以通过 >、==、< 进行比较。这里题目保证传入的数据是递减有序的。

输入样例 1：

5
35 12 8 7 3
10

输出样例 1：

35 12 10 8 7 3
Array size = 6

输入样例 2：

6
35 12 10 8 7 3
8

输出样例 2：

Insertion failed.
35 12 10 8 7 3
Array size = 6

*/

#include <stdio.h>
#include <stdlib.h>

#define kMaxSize 100
typedef enum { false, true } bool;

typedef int ElemSet;
typedef int Position; /* 整型下标，表示元素的位置 */
typedef struct ArrNode *ArrPtr;
struct ArrNode {
    ElemSet *data; /* 存储数据的数组；ElemSet是用户定义的数据类型 */
    int size;      /* 数组的大小 */
};

bool DecrSeqInsert(ArrPtr array, ElemSet x);

int main(void) {
    int i, n;
    ArrPtr array;
    ElemSet x;

    array = (ArrPtr)malloc(sizeof(struct ArrNode));
    scanf("%d", &n);
    array->size = n;
    array->data = (int *)malloc(sizeof(int) * kMaxSize);
    for (i = 0; i < n; i++) {
        scanf("%d", &array->data[i]);
    }
    scanf("%d", &x);
    if (DecrSeqInsert(array, x) == false) {
        printf("Insertion failed.\n");
    }
    printf("%d", array->data[0]);
    for (i = 1; i < array->size; i++) {
        printf(" %d", array->data[i]);
    }
    printf("\n");
    printf("Array size = %d\n", array->size);

    return 0;
}
/* 你的代码将被嵌在这里 */
bool DecrSeqInsert(ArrPtr array, ElemSet x) {
    if (array->size == kMaxSize) {
        return false;
    }
    int i;
    for (i = 0; i < array->size; i++) {
        if (array->data[i] == x) {
            return false;
        }
        if (array->data[i] < x) {
            break;
        }
    }
    for (int j = array->size; j > i; j--) {
        array->data[j] = array->data[j - 1];
    }
    array->data[i] = x;
    array->size++;
    return true;
}